#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//99.44%
class Solution0
{
  public:
	int findKthLargest(vector<int> &nums, int k)
	{
		sort(nums.begin(), nums.end());
		return nums[nums.size() - k];
	}
};
//29.65 %
class Solution
{
  public:
	int findKthLargest(vector<int> &nums, int k)
	{
		return nums[QuickSort(nums, 0, nums.size() - 1, k)];
	}
	int QuickSort(vector<int> &nums, int s, int e, int k)
	{
		if (s <= e)
		{
			int q = Partition(nums, s, e);
			if (q == k - 1)
				return q;
			if (q > k - 1)
				return QuickSort(nums, s, q - 1, k);
			return QuickSort(nums, q + 1, e, k);
		}
		return -1;
	}
	int Partition(vector<int> &nums, int s, int e)
	{
		int x = nums[e];
		int i = s - 1;
		for (int j = s; j < e; j++)
		{
			if (nums[j] > x)
			{
				i++;
				swap(nums[j], nums[i]);
			}
		}
		swap(nums[e], nums[i + 1]);
		return i + 1;
	}
};

int main()
{
	int nums[6] = {3, 2, 1, 5, 6, 4};
	int len = sizeof(nums) / sizeof(int);
	vector<int> myVector(nums, nums + len);
	cout << Solution().findKthLargest(myVector, 2) << endl;
	for (int i = 0; i < len - 1; i++)
	{
		cout << myVector[i] << " ";
	}
	cout << myVector[len - 1] << endl;
	return 0;
}
